128. 最长连续序列

128. 最长连续序列

function longestConsecutive(nums: number[]): number {
    const numSet = new Set(nums);
    let maxLength = 0;

    for (const num of numSet) {
        // 只有当 num 是连续序列的开头时才启动
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let length = 1;

            while (numSet.has(currentNum + 1)) {
                currentNum++;
                length++;
            }

            maxLength = Math.max(maxLength, length);
        }
    }

    return maxLength;
}

排序思路的限制

第一反应通常会是先排序再扫描：排序 O(N log N)，扫描 O(N)。这条路能做出来，但不满足题目要求的最优复杂度。

题目要求 O(N)，这意味着排序这条路可以直接排除，需要换成不依赖相邻比较的做法。

从序列起点出发

关键观察：在一个连续序列中，只有起点没有「前驱」。

对于元素 x，如果 x-1 也存在于集合中，那 x 不可能是某个连续序列的起点——它一定从属于以 x-1 结尾（或经过 x-1）的序列。只有 x-1 不存在时，x 才是一个序列的起始。

做法就变成：把所有数字放进 Set，然后只对那些「没有前驱」的数字，向后搜索连续序列的长度。每个数字最多被访问两次（一次作为起点检查，一次作为序列成员被后向扫描），所以总时间复杂度仍然是 O(N)。

为什么这是 O(N)

虽然内层有 while 循环，但 while 循环的总执行次数是受限于数组长度的——每个数字最多被 while 扫描一次（只有当它是某个序列的中间元素时），不会重复扫描。这是典型的均摊分析。